package cn.lccabc.array.no0633;

/**
 * @program: leet-code
 * @description: 平方数之和
 * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。
 *
 * 示例1:
 * 输入: 5
 * 输出: True
 * 解释: 1 * 1 + 2 * 2 = 5
 *
 * 示例2:
 * 输入: 3
 * 输出: False
 *
 * @author: LiCC
 * @create: 2020-01-01 19:14
 */
public class Solution {

    public static boolean judgeSquareSum(int c) {
        if (c == 1) return true;
        long c1 = c, l = 0, old = c, now = c;
        long threshold = c;
        while (threshold > 10000){
            threshold = new Double(Math.floor((double) threshold / 2)).longValue();
            old = now;
            now = now - threshold;
            if (now * now <= c){
                threshold = old - now;
            }
        }
        long r = old;
        while (l <= r){
            long sum = l*l + r*r;
            if (sum == c1){
                return true;
            } else if (sum < c1){
                l++;
            } else {
                r--;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int target = 13;
        boolean result = judgeSquareSum(target);
        System.out.println(result);
    }
}
